package me.mingshan.leetcode;

import java.util.HashSet;
import java.util.Set;

/**
 * https://leetcode.cn/problems/find-the-number-of-ways-to-place-people-i/
 *
 * 给你一个  n x 2 的二维数组 points ，它表示二维平面上的一些点坐标，其中 points[i] = [xi, yi] 。
 *
 *
 *
 * 计算点对 (A, B) 的数量，其中
 *
 * A 在 B 的左上角，并且
 * 它们形成的长方形中（或直线上）没有其它点（包括边界）。
 * 返回数量。
 *
 * @author hanjuntao
 * @date 2025/7/1 0001
 */
public class L_3025_find_the_number_of_ways_to_place_people_i {

    public static void main(String[] args) {
        int[][] points = {{1,1},{2,2},{3,3}};
        //System.out.println(numberOfPairs(points));

        int[][] points1 = {{6,2},{4,4},{2,6}};
        //System.out.println(numberOfPairs(points1));

        int[][] points2 = {{0,0},{0,3}};
        //System.out.println(numberOfPairs(points2));

        int[][] points3 = {{0,0},{0,6},{0,3},{1,0}};
        //System.out.println(numberOfPairs(points3));

        int[][] points4 = {{0,2},{3,0},{2,2},{3,2}};
        System.out.println(numberOfPairs(points4));
    }

    /**
     * 暴力解法
     *
     * 三个循环
     *
     * @param points
     * @return
     */
    private static int numberOfPairs(int[][] points) {
        if (points.length <= 1) {
            return 0;
        }
        if (points.length == 2) {
            for (int i = 0; i < points.length; i++) {
                int x = points[i][0];
                int y = points[i][1];

                for (int j = 0; j < points.length; j++) {
                    if (i != j) {
                        int x1 = points[j][0];
                        int y1 = points[j][1];
                        // 符合i的位置在j的左上方
                        if (x <= x1 && y >= y1) {
                            return 1;
                        }
                    }
                }
            }

            return 0;
        }

        Set<String> ans = new HashSet<>();

        for (int i = 0; i < points.length; i++) {
            int x = points[i][0];
            int y = points[i][1];

            for (int j = 0; j < points.length; j++) {
                if (i != j) {
                    int x1 = points[j][0];
                    int y1 = points[j][1];

                    if (ans.contains(x1 + ":" + y1 + ":" + x + ":" + y)) {
                        continue;
                    }

                    // 符合i的位置在j的左上方
                    if (x <= x1 && y >= y1) {
                        boolean existPoint = isExistPoint(points, i, j, x, y, x1, y1);

                        if (!existPoint) {
                            ans.add(x1 + ":" + y1 + ":" + x + ":" + y);
                            System.out.println("左上方坐标X:" + x + "左上方坐标Y:" + y );
                            System.out.println("右上方坐标X:" + x1 + "右上方坐标Y:" + y1);

                            System.out.println("--------------");
                        }
                    }
                }
            }
        }

        //ans = {HashSet@755}  size = 5
        // 0 = "2:2:3:0"
        // 1 = "0:2:3:2"
        // 2 = "0:2:2:2"
        // 3 = "2:2:3:2"
        // 4 = "3:2:3:0"

        return ans.size();
    }

    private static boolean isExistPoint(int[][] points,
                                        int i, int j, int x, int y, int x1, int y1) {
        // 判断矩形内是否有点
        for (int k = 0; k < points.length; k++) {
            if (k != i && k != j) {
                int x2 = points[k][0];
                int y2 = points[k][1];
                // 存在点在矩形内，那么这个j跳过
                if (x2 >= x && x2 <= x1 && y2 <= y && y2 >= y1) {
                   return true;
                }
            }
        }

        return false;
    }

}
